/*
    实现⼀个算法，⽤于实现最⼩找零纸币数。币种含：1、2、5、10、20、30、50、100元。要求：输⼊是⾦额，输出最少的找零纸币数。⽐如输⼊24，输出最⼩找零纸币数：3(⼀张20元、两张2元)。
    输⼊：24
    输出：3
    思路：贪心算法，从能找的最大面值开始给，不够向下一级取。
*/

pub fn dp_rec_mc(amount: u32) -> u32 {
    let denominations = [100, 50, 30, 20, 10, 5, 2, 1];
    let mut amount = amount;
    let mut count = 0;

    for &denomination in denominations.iter() {
        if amount == 0 {
            break;
        }
        count += amount / denomination;
        amount %= denomination;
    }
    count
}
